//
// Created by yangchao on 2022/6/6.
//130. 被围绕的区域: https://leetcode.cn/problems/surrounded-regions/
//

#include <vector>
using namespace std;

class Solve {
public:
    void solve(vector<vector<char>>& board) {
        if (board.size() == 0) return;
        for (int i = 0; i < board.size(); ++i) {
            dfs(board,i,0);
            dfs(board,i,board[0].size()-1);
        }
        for (int i = 1; i < board[0].size()-1; ++i) {
            dfs(board,0,i);
            dfs(board,board.size()-1,i);
        }
        for (int i = 0; i < board.size(); ++i) {
            for (int j = 0; j < board[0].size(); ++j) {
                if (board[i][j] == 'A') {
                    board[i][j] = 'O';
                } else if (board[i][j] == 'O') {
                    board[i][j] = 'X';
                }
            }
        }
    }

private:
    void dfs(vector<vector<char>>& board, int x, int y) {
        if (x < 0 || x >= board.size() || y < 0 || y >= board[0].size()) {
            return;
        }
        if (board[x][y] != 'O') return;
        board[x][y] = 'A';
        dfs(board,x+1,y);
        dfs(board,x-1,y);
        dfs(board,x,y+1);
        dfs(board,x,y-1);
    }
};
